#include<vector>
#include<numeric>
using namespace std;
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        //分解问题:一个环形问题 分解成两个线性问题
        //求最大 和最小的数组和 返回max(_max,sum-_min)
        //dp[i][0] 以i为结尾的最大子数组和 [1]以i为结尾的最小子数组和
        int sum=accumulate(nums.begin(),nums.end(),0);
        vector<int>min_dp(nums);vector<int>&max_dp=nums;
        max_dp[0]=nums[0],min_dp[0]=nums[0];
        int _max=nums[0],_min=nums[0];
        for(int i=1;i<nums.size();i++){
            min_dp[i]=min(min_dp[i-1]+nums[i],nums[i]);
            max_dp[i]=max(max_dp[i-1]+nums[i],nums[i]);
            _max=max(max_dp[i],_max);_min=min(min_dp[i],_min);
        }
        return max(_max,sum==_min?_max:sum-_min);
    }
};